package 回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class q40组合总和2 {
    class Solution {

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used ;
        int sum = 0;

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            used = new boolean[candidates.length];
            Arrays.sort(candidates); // 先进行排序
            backtracking(candidates, target, 0);
            return res;
        }

        public void backtracking(int[] candidates, int target, int startIndex) {
            if (sum > target) {
                return;
            }
            if (sum == target) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = startIndex; i < candidates.length; i++) {
                if(i>0 && candidates[i] == candidates[i-1] && !used[i-1]) continue;

                path.add(candidates[i]);
                used[i] = true;
                sum += candidates[i];
                backtracking(candidates, target, i+1);  // 从i开始，意味着可以包含重复
                path.remove(path.size() - 1);
                used[i] = false;
                sum -= candidates[i];
            }
        }
    }
}
